package com.nav.util;

public class BalancedTree<T extends Comparable<T>> {
	Node<T> root;
	public void insert(T n) {
		if(root == null)
			root = new Node<T>(n);
		else
			root = root.insert(n);
	}
	public int greaterCount(T n) {
		if(root == null)
			return 0;
		return root.greaterCount(n);
	}
	public String toString() {
		if(root == null)
			return null;
		return root.toString();
	}
	private static class Node<T extends Comparable<T>> {
		private T v;
		private int c = 1, h = 1, nc = 1;
		private Node<T> l, r;
		public Node(T v) {
			this.v = v;
		}
		private int balanceFactor() {
			return (l == null ? 0 : l.h) - (r == null ? 0 : r.h);
		}
		private void recalculateCount() {
			c = (l == null ? 0 : l.c) + (r == null ? 0 : r.c) + nc;
		}
		private void recalculateHeight() {
			h = Math.max((l == null ? 0 : l.h), (r == null ? 0 : r.h)) + 1;
		}
		private void recalculate() {
			recalculateCount();
			recalculateHeight();
		}
		public Node<T> insert(T n) {
			if(n.compareTo(v) > 0) {
				if(r == null)
					r = new Node<T>(n);
				else
					r = r.insert(n);
				recalculate();
				if(balanceFactor() < -1) {
					int rlh = r.l == null ? 0 : r.l.h, rrh = r.r == null ? 0 : r.r.h;
					if (rlh > rrh) {
						// this is the first step in the right-left case.
						Node<T> tr = r, trl = r.l, C = trl.r;
						tr.l = C;
						tr.recalculate();
						trl.r = tr;
						trl.recalculate();
						r = trl;
						recalculate();
					}
					// This brings us to the right-right case.
					Node<T> tr = r, B = tr.l;
					r = B;
					recalculate();
					tr.l = this;
					tr.recalculate();
					return tr;
				}
			} else if(n.compareTo(v) < 0) {
				if(l == null)
					l = new Node<T>(n);
				else
					l = l.insert(n);
				recalculate();
				if(balanceFactor() > 1) {
					int llh = l.l == null ? 0 : l.l.h, lrh = l.r == null ? 0 : l.r.h;
					if (lrh > llh) {
						// this is the first step in the left-right case.
						Node<T> tl = l, tlr = l.r, B = tlr.l;
						tl.r = B;
						tl.recalculate();
						tlr.l = tl;
						tlr.recalculate();
						l = tlr;
						recalculate();
					}
					// This brings us to the left-left case.
					Node<T> tl = l, C = tl.r;
					l = C;
					recalculate();
					tl.r = this;
					tl.recalculate();
					return tl;
				}
			}
			else {
				nc++;
				recalculateCount();
			}
			return this;
		}
		public int greaterCount(T cn) {
			if(cn.compareTo(v) > 0)
				return r.greaterCount(cn);
			if(cn.compareTo(v) < 0)
				return (r == null ? 0 : r.c) + nc + l.greaterCount(cn);
			return r == null ? 0 : r.c;
		}
		public String toString() {
			if(l == null && r == null)
				return v + ":" + nc;
			return "{" + l + ", " + v + ":" + nc + ", " + r + "}";
		}
	}
}
